1. Field of the Invention
This invention relates to apparatus and methods for efficiently rolling back and retrying conflicted speculative threads in SMP environments using distributed tokens.
2. Background of the Invention
Speculative execution (SE), also known as thread-level speculation (TLS), requires in-order start, as well as in-order commit of threads. The workload is typically split into a sequence of work units, referred to as absolute thread numbers (ATNs), that are assigned to a group of n threads, in sequence. A complete round of allocation assigns work units to threads T0, T1, . . . , Tn-2, Tn-1. By dispatching the threads in order, and committing them in order, program semantics are preserved.
The manner in which current SMP systems perform speculative execution is inefficient and difficult to debug. For example, current SMP systems require the kernel to track the number of conflict events (i.e., events causing threads to abort). When the number of conflict events reaches a threshold, the kernel modifies a global variable, referred to herein as an “allocation token,” to initiate retries of the aborted threads. Threads operating in user space also need to update the allocation token. As a result, a lock is required to protect the allocation token. Implementing a lock that is shared between the kernel and the SMP runtime makes the design both inefficient as well as difficult to debug. For example, a sequence of code used to start speculation is shown below. A similar locking sequence is also present in the decision code.
while {lock allocation_token;if (allocation_token == thread's ATN)proceed to obtain specID;elseunlock allocation_token;continue;}
In view of the foregoing, what are needed are apparatus and methods to more efficiently roll back and retry conflicted speculative threads in SMP environments. Ideally, such apparatus and methods will remove the locking requirement associated with the allocation token.